package site.wanjiahao.sort.compare;

import site.wanjiahao.sort.Sort;

public class InsertionSort3<E extends Comparable<E>> extends Sort<E> {

    /**
     * 插入排序，将排序数组分为两部分，前部分是已经拍好序的数组，后半部分是待排序的数组
     *      在未排序数组选择当前数组，插入到已经排好序数组的某个位置
     *
     *      对于比较，因为前半段已经是排好顺序的，所以可以使用二分查找，找出对于的索引，这样效率会更加高效
     *
     *
     */
    @Override
    protected void sort() {
        for (int i = 1; i < array.length; i++) {
            E cur = array[i];
            int searchIndex = search(i, cur);
            // 元素挪动
            if (i - searchIndex >= 0)
                System.arraycopy(array, searchIndex, array, searchIndex + 1, i - searchIndex);

            array[searchIndex] = cur;
        }
    }

    // 查询到插入位置
    public int search(int end, E cur) {
        int begin = 0;
        // 结束循环
        while (end > begin) {
            int mid = (begin + end) >> 1;
            if (cmp(cur, array[mid]) >= 0) {
                // 右部分
                begin = mid + 1;
            } else {
                end = mid;
            }
        }
        return begin;
    }
}
